perm filename A68.TEX[106,RWF] blob sn#807783 filedate 1985-09-20 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\parskip 6pt
\rm
\line{\sevenrm a68.tex[106,phy] \today\hfill}

\bigskip
{\narrower\smallskip\noindent
{\bf Exercise: Dynamic Programming.}

\vskip 2truein

\noindent
We are given a sequence of points by their coordinates. We want to find,
as shown above, a small number of straight lines that closely fit the points.

If the points have coordinates $(x↓i,y↓i)$ ($1≤i≤n$), we can find the best
single line by this algorithm:

Compute
$$\eqalign{SX&=\sum x↓i\cr
SY&=\sum y↓i\cr
SXX&=\sum x↓i↑2\cr
SXY&=\sum x↓iy↓i\cr
SYY&=\sum y↓i↑2\cr
\vdots\cr}$$
The error minimized is measured by the sum of the squares of the distances
of the lines from the points, which is \dots .

Develop an algorithm which, for each $N$ up to (say)~10, finds the best
broken line of $N$~segments, in the sense of minimizing the sum of the
squares of the distances from a point to a line segment.
\smallskip}


\bigskip
\line{\copyright 1985 Robert W. Floyd\hfill}
\line{First draft (not published) March 26, l985.\hfill}

\bye